package leetcode.array;

/**
 * @author Cheng Jun
 * Description: 数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。
 *
 * 每当爬上一个阶梯都要花费对应的体力值，一旦支付了相应的体力值，就可以选择向上爬一个阶梯或者爬两个阶梯。
 *
 * 请找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/GzCJIP
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @version 1.0
 * @date 2022/1/9 23:33
 * 二刷 动态规划 面试题
 */
public class minCostClimbingStairs {

    public static void main(String[] args) {
        minCostClimbingStairs(new int[]{1,100,1,1,1,100,1,1,100,1});
        System.out.println(minCostClimbingStairs1(new int[]{1, 2}));
    }

    // 不推荐使用，因为dp的定义不够简单明了。请参考 minCostClimbingStairs1
    static public int minCostClimbingStairs(int[] cost) {
        int length = cost.length;
        // dp[i] 指的是，从第i层往上跳一次或两次的最小体力值
        int[] dp = new int[length];
        dp[0] = cost[0];
        dp[1] = cost[1];
        for(int i = 2; i < cost.length; i++){
            dp[i] = Math.min(dp[i-2], dp[i-1]) +cost[i];
        }
        // 最后两阶楼梯，往上跳一次或两次的体力值取最小值
        return Math.min(dp[length-1],dp[length -2]);
    }

    // 推荐
    static public int minCostClimbingStairs1(int[] cost) {
        int n = cost.length;
        // dp[i] 登上第i层所需最小的体力值
        int[] dp = new int[n + 1];
        dp[0] = dp[1] = 0;
        for (int i = 2; i <= n; i++) {
            // 动态转移方程的理解：dp[i] 是从dp[i-1] 或者 dp[i-2] 跳上来的
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[n];
    }

}
